package com.feiyue.learning.graph;

import java.util.Scanner;

/**
 * 解决最小生成树：
 *
 *        3...4
 *       ..  ...
 *      1 . . . 6
 *       ...  ..
 *        2...5
 * @author  feiyue
 * @date  2020/4/6
 */
public class KruskalDemo {

    // 定义一个数组存放各个顶点对应的根顶点(用于求顶点的并集)
    // 树形结构存储, f[i] 存放是顶点 i 的父顶点, f[i] = i 则是最终的根顶点
    static int[] f = new int[7];

    public static void main(String[] args) {

        // 表示图中顶点数
        int n = 6;

        // 表示图中边的数量
        int m = 9;

        // 存储边的数组
        Edge[] es = new Edge[10];
        for (int i = 1; i <= m; i++) {
            // 初始化 m 条边
            Scanner sc = new Scanner(System.in);
            int sNode = sc.nextInt();
            int tNode = sc.nextInt();
            int w = sc.nextInt();
            Edge e = new Edge(sNode, tNode, w);
            es[i] = e;
        }

        // 对边按照权重进行排序
        quickSort(es, 1, m);

        for (int i = 1; i <= n; i++) {
            // 初始化根顶点为自己
            f[i] = i;
        }

        /*
         *  Kruskal 算法核心
         */
        int count = 0; // 计数, 记录添加的边数
        int sum = 0; // 求和, 计算路径权重之和
        for (int i = 1; i <= m; i++) {

            // 判断当前选择的边的两个顶点是否连通
            if (merge(es[i].s, es[i].t)) {
                count++;
                sum += es[i].w;
            }

            if (count == (n - 1)) {
                break;
            }
        }

        System.out.println("最短路径总和：" + sum);
    }

    private static boolean merge(int s, int t) {
        int t1, t2;
        t1 = getF(s);
        t2 = getF(t);
        if (t1 != t2) {
            // 起始顶点作为父类顶点
            f[t2] = t1;
            return true;
        }
        return false;
    }

    private static int getF(int s) {
        if (f[s] == s) {
           return s;
        } else {
            f[s] = getF(f[s]);
            return f[s];
        }
    }

    private static void quickSort(Edge[] es, int begin, int end) {
        if (begin >= end) {
            return;
        }

        int i = begin;
        int j = end;
        int base = es[begin].w;
        while (i != j) {
            while (es[j].w >= base && j > i) {
                j--;
            }

            while (es[i].w <= base && i < j) {
                i++;
            }

            if (j > i) {
                exchange(es, i, j);
            }
        }
        exchange(es, begin, i);

        quickSort(es, begin, i - 1);
        quickSort(es, i + 1, end);
    }

    private static void exchange(Edge[] es, int i, int j) {
       Edge temp = es[i];
       es[i] = es[j];
       es[j] = temp;
    }
}

class Edge {
    // 边起始顶点
    int s;

    // 边终止顶点
    int t;

    // 边的权重
    int w;

    public Edge(int s, int t, int w) {
        this.s = s;
        this.t = t;
        this.w = w;
    }
}
